package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.knowledge.KBackTracking;
import pro.softzhang.algo.flag.theme.TMathCombination;

import java.util.LinkedList;
import java.util.List;

/**
 *
 */
@TMathCombination
public class LC39_CombinationSum {
    public static void main(String[] args) {

    }

    /**
     * 
     */
    @KBackTracking
    static
    class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> r = new LinkedList<>();
            LinkedList<Integer> c = new LinkedList<>();
            combinationSum0(candidates, target, 0, c, r);
            return r;
        }

        private void combinationSum0(int[] nums, int target, int i, LinkedList<Integer> c, List<List<Integer>> r) {
            if(target == 0) {
                r.add(new LinkedList<>(c));
                return;
            }

            if(target > 0 && i < nums.length) {
                combinationSum0(nums, target, i + 1, c, r);
                c.add(nums[i]);
                combinationSum0(nums, target - nums[i], i, c, r);
                c.removeLast();
            }
        }
    }
}
